package me.algo.rec;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Objects;
import java.util.Set;
import java.util.stream.Collectors;

/**
 * @author guozheng
 * @date 2024/5/10
 */
public class R2 {
    /**
     * 491. 非递减子序列
     * @param nums
     * @return
     */
    public static List<List<Integer>> findSubsequences(int[] nums) {
        if (Objects.isNull(nums) || nums.length < 2) {
            return new ArrayList<>();
        }
        int len = nums.length;
        int minLen = 2;
        LinkedList<Seq> seqs = new LinkedList<>();
        for (int i = 0; i <= len - minLen; i++) {
            List<Integer> headEle = new ArrayList<>();
            headEle.add(nums[i]);
            List<Integer> restEle = new ArrayList<>();
            for (int j = i + 1; j < nums.length; j++) {
                restEle.add(nums[j]);
            }
            if (restEle.isEmpty()) {
                continue;
            }
            Seq seq = new Seq(headEle, restEle);
            seqs.add(seq);
        }
        Set<List<Integer>> rtn = new HashSet<>();
        while (!seqs.isEmpty()) {
            int size = seqs.size();
            while (size > 0) {
                size--;
                Seq seq = seqs.removeFirst();
                List<Integer> head = seq.head;
                List<Integer> tail = seq.tail;
                while (!tail.isEmpty()) {
                    Integer preLast = head.getLast();
                    Integer next = tail.removeFirst();
                    if (next >= preLast) {
                        List<Integer> nst = new ArrayList<>(head);
                        nst.add(next);
                        if (nst.size() >= minLen) {
                            rtn.add(nst);
                        }
                        if (!tail.isEmpty()) {
                            Seq nxtSeq = new Seq(nst, new ArrayList<>(tail));
                            seqs.addLast(nxtSeq);
                        }
                    }
                }

            }
        }
        return new ArrayList<>(rtn);
    }

    record Seq(List<Integer> head, List<Integer> tail) {

    }


    /**
     * 39. 组合总和
     * @param candidates
     * @param target
     * @return
     */
    public static List<List<Integer>> combinationSum(int[] candidates, int target) {
        if (Objects.isNull(candidates) || candidates.length == 0) {
            return new ArrayList<>();
        }
        Set<List<Integer>> rtn = new HashSet<>();
        Set<Integer> cdset = toSet(candidates);
        LinkedList<Candi> que = new LinkedList<>();
        for (int candidate : candidates) {
            if (candidate <= target) {
                int remain = target - candidate;
                Set<Integer> candiList = cdset.stream().filter(v -> v <= remain).collect(Collectors.toSet());
                List<Integer> head = new ArrayList<>();
                head.add(candidate);
                Candi candi = new Candi(head, candiList);
                que.add(candi);
            }
        }
        while (!que.isEmpty()) {
            int size = que.size();
            while (size > 0) {
                size--;
                Candi candi = que.removeFirst();
                int sum = candi.sum();
                if (sum == target) {
                    rtn.add(candi.headList());
                } else if (sum < target) {
                    Set<Integer> candis = candi.candiList();
                    List<Integer> headList = candi.headList();
                    for (Integer i : candis) {
                        int nsm = sum + i;
                        if (nsm < target) {
                            int rmn = target - nsm;
                            Set<Integer> rnSets = candis.stream().filter(v -> v <= rmn).collect(Collectors.toSet());
                            if (!rnSets.isEmpty()) {
                                List<Integer> hl = new ArrayList<>(headList);
                                hl.add(i);
                                Candi nxt = new Candi(hl, rnSets, nsm);
                                que.add(nxt);
                            }
                        } else if (nsm == target) {
                            List<Integer> hl = new ArrayList<>(headList);
                            hl.add(i);
                            rtn.add(hl);
                        }
                    }
                }
            }
        }
        return rtn.stream().map(v -> v.stream().sorted().toList()).distinct().collect(Collectors.toList());
    }

    record Candi(List<Integer> headList, Set<Integer> candiList, int sum) {
        public Candi(List<Integer> headList, Set<Integer> candiList) {
            this(headList, candiList, sum(headList));
        }

        private static int sum(List<Integer> lst) {
            if (Objects.isNull(lst)) {
                return 0;
            }
            int sm = lst.stream().mapToInt(Integer::intValue).sum();
            return sm;
        }
    }

    private static Set<Integer> toSet(int[] candidates) {
        Set<Integer> cdset = new HashSet<>();
        for (int candidate : candidates) {
            cdset.add(candidate);
        }
        return cdset;
    }


    /**
     * 40. 组合总和 II
     * @param candidates
     * @param target
     * @return
     */
    public static List<List<Integer>> combinationSum2(int[] candidates, int target) {
        if (Objects.isNull(candidates) || candidates.length == 0) {
            return new ArrayList<>();
        }
        LinkedList<Cmb> que = new LinkedList<>();
        Set<List<Integer>> rtn = new HashSet<>();
        List<Integer> cdList = toList(candidates);
        for (int i = 0; i < candidates.length; i++) {
            int candidate = candidates[i];
            if (candidate <= target) {
                int rm = target - candidate;
                List<Integer> nxtLst = cdList.stream().skip(i + 1).filter(v -> v <= rm).collect(Collectors.toList());
                List<Integer> head = new ArrayList<>();
                head.add(candidate);
                if (candidate == target) {
                    rtn.add(head);
                } else if (!nxtLst.isEmpty()) {
                    Cmb cmb = new Cmb(head, nxtLst, candidate);
                    que.add(cmb);
                }
            }
        }
        while (!que.isEmpty()) {
            Cmb cmb = que.removeFirst();
            List<Integer> usd = cmb.usd();
            List<Integer> rmd = cmb.rmd();
            int sum = cmb.sum();
            for (int i = 0; i < rmd.size(); i++) {
                Integer nxt = rmd.get(i);
                int nsm = nxt + sum;
                List<Integer> lst = new ArrayList<>(usd);
                lst.add(nxt);
                if (nsm == target) {
                    rtn.add(lst);
                } else if (nsm < target) {
                    int rmn = target - nsm;
                    List<Integer> nxtr = rmd.stream().skip(i + 1).filter(v -> v <= rmn).collect(Collectors.toList());
                    if (!nxtr.isEmpty()) {
                        Cmb nt = new Cmb(lst, nxtr, nsm);
                        que.addLast(nt);
                    }
                }
            }
        }


        return rtn.stream().map(l -> l.stream().sorted().toList()).distinct().toList();
    }


    public static List<Integer> toList(int[] nums) {
        if (Objects.isNull(nums)) {
            return new ArrayList<>();
        }
        List<Integer> res = new ArrayList<>();
        for (int num : nums) {
            res.add(num);
        }
        return res;
    }

    record Cmb(List<Integer> usd, List<Integer> rmd, int sum) {
        public Cmb(List<Integer> usd, List<Integer> rmd) {
            this(usd, rmd, sum(usd));
        }

        static int sum(List<Integer> lst) {
            if (Objects.isNull(lst)) {
                return 0;
            }
            return lst.stream().mapToInt(Integer::intValue).sum();
        }
    }
    public static void main(String[] args) {
        int[] ints = {10,1,2,7,6,1,5};
        int t = 8;
        List<List<Integer>> lists = combinationSum2(ints, 8);
        System.out.println(lists);

    }
}
